/**
 * 在数组中找第k大的元素，给出下标
 * 方法1：排序后直接给出下标，但是做了很多没用的工作
 * 方法2：使用快排的思想，不断的划分
 */

/**
 * @param a 数组
 * @param left 左端，下标从0开始，答案中判断是k大元素的时候使用的是left==k，这个判断是不对的
 * @param right 右端
 * @param k 找第k大的元素
 */
int k_min(int a[],int left,int right,int k){
    int pivot=a[left];
    int temp_left=left;
    int temp_right=right;

    //从左往右，从右往左不断查找，使得数组左半边元素都小于pivot
    //右边都大于pivot
    while (left<right)
    {
        while (left<right&&a[right]>=pivot)//这里和pivot相等的元素都不动
        {
            --right;
        }
        a[left]=a[right];
        while (left<right&&a[left]<=pivot)
        {
            ++left;
        }
        a[right]=a[left];
    }
    a[left]=pivot;
    //下面是判断pivot的位置，当pivot的位置正好位于k下标时，就是我们要找的元素
    //否则，根据pivot所处的位置，递归查找
    //如果pivot位于右半边时，那么就递归查找左半部分
    if(left==k-1){//这里要改成k-1,left从0开始，那么left=k的时候，是第k+1大的
        return a[left];
    }else if(left>k){
        return k_min(a,temp_left,left-1,k);//这里递归，所有下标都是原始数组的下标，不会因为分裂，子数组下标重新0开始
    }else{
        return k_min(a,left+1,temp_right,k);
    }
}

/**
 * 这里给出一个例子：
 * {4,2,1,3,5,6}要找第五大的元素，也就是5
 * 现在pivot=4，经过变换后 {3,2,1,4,5,6} 4所处的位置是
 * 
 */
#include<stdio.h>
int main(void){
    int n=6;
    int arr[]={4,2,1,3,5,6};
    int res=k_min(arr,0,n-1,5);//找第5大的元素
    printf("%d \n",res);
}